import java.util.Stack;
//设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈
public class MinStack {
    //首先需要一个普通栈和一个专门存储最小值的最小栈
    Stack<Integer> myStack;
    Stack<Integer> minStack;
    public MinStack() {
        myStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        //首先判断是否是第一次插入
        if(myStack.isEmpty()){
            myStack.push(val);
            minStack.push(val);
        }else {
            //如果不是第一次插入那么就判断要插入的数据和最小栈栈顶元素哪个小
            //如果要插入的值小于等于最小值，那么都需要插入，否则只需插入普通栈
            if(val <= minStack.peek()){
                minStack.push(val);
                myStack.push(val);
            }else {
                myStack.push(val);
            }
        }
    }

    public void pop() {
        //判断栈帧空间是否为空
        if(myStack.isEmpty()){
            return;
        }
        //再判断要删除的栈顶元素是不是最小值
        int val = myStack.pop();
        //不可以将myStack.pop()和minStack.peek()直接比较+
        if(val == minStack.peek()){
            minStack.pop();
        }
    }

    public int top() {
        //判断栈帧空间是否还存有数据
        if(myStack.isEmpty()){
            return -1;
        }else {
            //如果有元素，那么可以直接返回栈顶元素
            return myStack.peek();
        }
    }

    public int getMin() {
        //判断最小栈中是否为空
        if(minStack.isEmpty()){
            return -1;
        }else {
            return minStack.peek();
        }
    }
}
